﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MessageWorkflow.Graph
{
    /// <summary>
    /// Adjacency list implementation of the graph
    /// </summary>    
    public class AdjacencyListGraph<T> : IGraph<T>
    {
        #region Protected Properties

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", 
            Justification = "NodeList should be both abstract to the value type (T) as well as the underlying collection")]
        protected ICollection<AdjacencyListGraphNode<T>> NodeList { get; private set; }

        #endregion // Protected Properties

        #region Constructor

        public AdjacencyListGraph()
        {
    
#if WINDOWS_PHONE
            NodeList = new List<AdjacencyListGraphNode<T>>();
#else
            // default
            NodeList = new HashSet<AdjacencyListGraphNode<T>>();
#endif
        }

        #endregion // Constructor

        #region Properties

        public IEnumerable<T> Nodes
        {
            get
            {
                return from n in NodeList
                       select n.Value;
            }
        }

        #endregion // Properties

        #region Methods

        public void Add(T value)
        {
            AdjacencyListGraphNode<T> newNode = new AdjacencyListGraphNode<T>()
            {
                Value = value
            };

            NodeList.Add(newNode);
        }

        public void Add(T value, IEnumerable<T> dependencies)
        {
            Add(value);
            AddPredecessors(value, dependencies);
        }

        public void AddPredecessors(T value, IEnumerable<T> predecessors)
        {
            if (predecessors != null)
            {
                AdjacencyListGraphNode<T> currentNode = FindNode(value);
                if (currentNode == null)
                    throw new ArgumentException("Unknown entry", "value");

                foreach (T dependency in predecessors)
                {
                    if (!currentNode.Dependencies.Contains(dependency))
                    {
                        if (!Nodes.Contains(dependency))
                        {
                            Add(dependency);
                        }

                        currentNode.Dependencies.Add(dependency);
                    }
                }

                // make sure there are no strongly connected components
                IEnumerable<IEnumerable<T>> stronglyConnectedComponents = FindStronglyConnectedComponents();

                if (stronglyConnectedComponents.Any())
                {
                    // restore state
                    RemovePredecessors(value, predecessors);
                    throw new RecursivePathException("Recursive path detected while adding predecessors");
                }
            }
       } 

        public void Remove(T value)
        {
            // lazy delete
            AdjacencyListGraphNode<T> currentNode = FindNode(value);
            if (currentNode == null)
            {
                throw new ArgumentException("Unknown entry", "value");
            }

            NodeList.Remove(currentNode);
        }

        public void RemovePredecessors(T value, IEnumerable<T> predecessors)
        {
            if (predecessors != null)
            {
                AdjacencyListGraphNode<T> currentNode = FindNode(value);
                if (currentNode == null)
                {
                    throw new KeyNotFoundException("The value was not known in the graph");
                }

                foreach (T dependency in predecessors)
                {
                    currentNode.Dependencies.Remove(dependency);
                }
            }
        }

        public IEnumerable<T> GetPredecessors(T value)
        {
            AdjacencyListGraphNode<T> currentNode = FindNode(value);
            if (currentNode == null)
            {
                throw new KeyNotFoundException("The value was not known in the graph");
            }
            else if (currentNode.Dependencies == null)
            {
                return Enumerable.Empty<T>();
            }
            else
            {
                // since were using lazy deletion (not deleting existing predecessors when deleting, only return predecessors to nodes that are still existing
                return from dependency in currentNode.Dependencies
                       where Nodes.Contains(dependency)
                       select dependency;
            }
        }

        public bool Contains(T value)
        {
            AdjacencyListGraphNode<T> existing = FindNode(value);

            return existing != null;
        }

        public void Clear()
        {
            NodeList.Clear();
        }

        #endregion // Methods

        #region Helpers

        protected AdjacencyListGraphNode<T> FindNode(T value)
        {
            var existing = from n in NodeList
                           where object.Equals(n.Value, value)
                           select n;

            return existing.FirstOrDefault();
        }

        protected virtual IEnumerable<IEnumerable<T>> FindStronglyConnectedComponents()
        {
            Algorithm.TarjanAlgorithm<T> strategy = new Algorithm.TarjanAlgorithm<T>(this);
            return strategy.FindStronglyConnectedComponents();
        }

        #endregion // Helpers
    }
}
